package advanced.class06;

import java.util.HashMap;

// 左神第六课——
// 求一个全是整数的数组中累加和为k的最大子数组的长度
public class Code_04_LongestSumSubArrayLengthInPositiveArray {

	//+++++++++++++++++++解法一： 双指针++++++++++++++++++++++

	/**
	 * 如果累加和超过sum，则左边缩一个
	 * 如果累加和小于sum，则右边扩一个
	 * 如果累加和等于sum，则更新maxLen的值
	 * @param arr
	 * @param k
	 * @return
	 */
	public static int getMaxLength(int[] arr, int k) {
		if (arr == null || arr.length == 0 || k <= 0) {
			return 0;
		}
		int L = 0;
		int R = 0;
		int sum = arr[0];
		int len = 0;
		while (R < arr.length) {
			if (sum == k) {
				len = Math.max(len, R - L + 1);
				sum -= arr[L++];
			} else if (sum < k) {
				R++;
				if (R == arr.length) {
					break;
				}
				sum += arr[R];
			} else {
				sum -= arr[L++];
			}
		}
		return len;
	}

	public static int[] generatePositiveArray(int size) {
		int[] result = new int[size];
		for (int i = 0; i != size; i++) {
			result[i] = (int) (Math.random() * 10) + 1;
		}
		return result;
	}

	public static void printArray(int[] arr) {
		for (int i = 0; i != arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		int len = 20;
		int k = 15;
		int[] arr = generatePositiveArray(len);
		printArray(arr);
		System.out.println(getMaxLength(arr, k));
		System.out.println(getMaxLen(arr, k));
	}

	//++++++++++自己写的方法(使用map存储中间值)++++++++++++
	public static int getMaxLen(int[] arr, int aim){
		HashMap<Integer,Integer> map = new HashMap<>();
		map.put(0,-1);
		int sum = 0;
		int maxLen = 0;
		for (int i = 0; i < arr.length; i++) {
			sum += arr[i];
			if(map.containsKey(sum - aim)){
				maxLen = Math.max(maxLen,i - map.get(sum - aim));
			}
			if(!map.containsKey(sum)){
				map.put(sum,i);
			}
		}
		return maxLen;
	}


}
